# 最小编辑距离

# 通过两个指针在两个字符串上移动
def minDistance(s1, s2):
    m = len(s1)
    n = len(s2)

    dp = [[0 for _ in range(n)] for _ in range(m)]  # 将s1[0:i]变为s2[0:j]所需要的最小操作数为dp[i][j]

    # base case
    for i in range(1, m):
        dp[i][0] = i  # s1还有i个字符，而s2已经没有字符了，要想把s1变为s2，则还需要再执行i步删除

    for j in range(1, n):
        dp[0][j] = j  # s2还有j个字符，而s1已经没有字符了，要想把s1变为s2，则还需要再执行j步删除

    for i in range(1, m):
        for j in range(1, n):
            if s1[i] == s2[j]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j],  # 删除
                    dp[i][j-1],  # 插入
                    dp[i-1][j-1] # 替换
                )

    return dp[m-1][n-1]

s1 = "rad"
s2 = "apple"
print("{} {} 编辑距离 {} ".format(s1, s2, minDistance(s1, s2)))
